All natural numbers greater than 1 have a unique prime factorization.
GCD is the greatest common divisor.
LCM is the least common multiple.
$${a = p_1^{k_1} p_2^{k_2} p_3^{k_3} \cdots p_n^{k_n} }$$
$${b = p_1^{m_1} p_2^{m_2} p_3^{m_3} \cdots p_n^{m_n} }$$
$${\text{gcd}(a,b) = p_1^{\text{min}(k_1,m_1)} p_2^{\text{min}(k_2,m_2)} \cdots p_n^{\text{min}(k_n,m_n)} }$$
$${\text{lcm}(a,b) = p_1^{\text{max}(k_1,m_1)} p_2^{\text{max}(k_2,m_2)} \cdots p_n^{\text{max}(k_n,m_n)} }$$
$${a = p_1^{k_1} p_2^{k_2} p_3^{k_3} \cdots p_m^{k_m} }$$
$${n = \text{number of divisors} = (k_1 + 1)(k_2 + 1) (k_3 + 1) \cdots (k_m + 1) }$$
$${\text{product of divisors} = a^{n/2} }$$
$${\text{sum of divisors} = \frac{p_1^{k_1 + 1} - 1}{p_1 - 1} \frac{p_2^{k_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_m^{k_m + 1} - 1}{p_m - 1} }$$
$${\text{if } a \mid b }$$
$${\text{then }an = b }$$
2
Divisibility by 2 requires that the number is even.
3
Divisibility by 3 requires that sum of the digits is divisible by 3.
4
Divisibility by 4 requires that the last 2 digits are divisible by 4.
5
Divisibility by 5 requires that last digit is either 5 or 0.
6
Divisibility by 6 requires that number is even and divisible by 3.
7
For 7 take the first 2 digits from the left and replace those 2 digits with that 2 digit number mod 7.
Repeat this process until you can determine if the remaining number can be divided by 7 .
8
Divisibility by 8 requires that the last 3 digits are divisible by 8.
9
Divisibility by 9 requires that sum of the digits is divisible by 9.
10
Divisibility by 5 requires that last digit is 0.
11
Divisibility by 11 requires that alternating sum of the digits (from either side) is divisible by 11.
12
Divisibility by 12 requires that number is divisible by 3 and 4.
14
Divisibility by 14 requires that number is divisible by 2 and 7.
15
Divisibility by 15 requires that number is divisible by 3 and 5.
37
Take the number in groups of 3 digits from right to left and add them together. If the result is divisible by 37 then the number is divisible by 37.
$${\text{if } a \equiv b {\pmod n} }$$
$${\text{then } n \mid a - b }$$
$${\text{if } a \equiv b {\pmod n} \text{ and } d \mid n }$$
$${\text{then } a \equiv b {\pmod d} }$$
$${\text{if } a \equiv b {\pmod n} }$$
$${\text{then } ac \equiv bc {\pmod {nc}} }$$
$${\text{if } a \equiv b {\pmod n} }$$
$${\text{then } a^k \equiv b^k {\pmod n} }$$
If a and n are relatively prime then there is a solution for \(a^{-1} {\pmod {n}} \)
The inverse can be found using Bezout's identity for gcd(a,n) = 1:
$${ax + by = 1}$$
For difficult inverses with large numbers it is recommended to use the Euclidean Algorithm.
You can also use the following formula to find the inverse:
$${a^{-1} {\pmod {n}} = a^{\phi(n) - 1} {\pmod {n}}}$$
Sophie-Germain Primes
A prime p where 2p + 1 is also a prime.
Example 11 is a Sophie-Germain prime because 23 is also prime.
Fermat Primes
A Fermat number is defined as \(F_n = 2^{2^n} + 1 \)
A Fermat prime is just a prime Fermat number.
There are only 5 Fermat primes:
\(F_0 = 3, F_1 = 5,F_2 = 17,F_3 = 257,F_4 = 65537\)
And these are the only primes of the form \(2^n + 1 \)
Fibonacci Primes
Fibonacci Primes are just primes within the Fibonacci Sequence:
1,1,2,3,5,8,13,21,34,55...
An interesting result is that Fibonacci Primes also have a prime index except for 4.
This is because in the Fibonacci sequence:
$${a \mid b \to F_a \mid F_b}$$
But not every Fibonacci number with a prime index is a prime.
So the first few Fibonacci Primes are:
$${F_3=2, F_4=3, F_5=5, F_7 = 13, F_{11} = 89, \cdots }$$
Mersenne Primes
Mersenne Primes are of the form \(2^n - 1\) where n is prime.
Some examples: 3, 7, 31, 127...
The value of n must be prime but it doesn't gaurantee a prime since \(2^{11} - 1 = 2047 = 23 \cdot 89 \)
$${ }$$
$${ }$$
A natural number n greater than 1 is a prime if and only if \( (n - 1)! \equiv n-1 {\pmod n} \)
$${(p - 1)! \equiv p-1 {\pmod p} \equiv -1 {\pmod p} }$$
$${(p - 2)! \equiv 1 {\pmod p} }$$
$${(p - 3)! \equiv (p-2)^{-1} {\pmod p} \equiv (-2)^{-1} {\pmod p} }$$
For integers a and b with greatest common divisor d there exists integers x and y such that \( ax + by = d \).
For prime number p where \(p \nmid a \) :
$${a^{p-1} \equiv 1 {\pmod p} }$$
$${a^{p} \equiv a {\pmod p} }$$
Assume n has the prime factorization: \(n = p_1^{k_1} p_2^{k_2} p_3^{k_3} \cdots \)
$${\phi(n) = n \frac{p_1 - 1}{p_1} \frac{p_2 - 1}{p_2} \frac{p_3 - 1}{p_3} \cdots }$$
$${\phi(n) = p_1^{k_1 - 1} (p_1 - 1) p_2^{k_2 - 1} (p_2 - 1) p_3^{k_3 - 1} (p_3 - 1)\cdots }$$
$${\phi(mn) = \phi(m) \phi(n) \text{ if } gcd(m,n) = 1}$$
$${\phi(2^n) = \frac{2^n}{2} = 2^{n-1} }$$
$${\phi(n) = \phi(2^k 3^m) = \frac{n}{3} }$$
For a single prime p: \(\phi(p) = p - 1 \)
$${a^{\phi(n)} \equiv 1 {\pmod n} \text{ if } gcd(a,n) = 1}$$